package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;





import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;
import util.datastructure.ListNode;

/*
 * 
原题　
		 Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
	
	For example,
	Given 1->2->3->3->4->4->5, return 1->2->5.
	Given 1->1->1->2->3, return 2->3. 
题目大意

解题思路
	和之前那道 ( http://www.cnblogs.com/grandyang/p/4066453.html ) 
	不同的地方是这里要删掉所有的重复项，由于链表开头可能会有重复项，被删掉的话头指针会改变，而最终却还需要返回链表的头指针。
	所以需要定义一个新的节点，然后链上原链表，然后定义一个前驱指针和一个现指针，
	每当前驱指针指向新建的节点，现指针从下一个位置开始往下遍历，遇到相同的则继续往下，直到遇到不同项时，把前驱指针的next指向下面那个不同的元素。
	如果现指针遍历的第一个元素就不相同，则把前驱指针向下移一位。代码如下：
 * @Date 2017-10-03 21：48
 */
public class _082_Remove_Duplicates_from_Sorted_List_II {
    public ListNode deleteDuplicates(ListNode head) {
    	ListNode tHead = new ListNode(-1);			//临时头 
    	tHead.next = head;
    	ListNode pre = tHead, cur;
    	while (pre.next != null) {
    			cur = pre.next;
    			while (cur.next!=null && cur.next.val==cur.val)
    				cur = cur.next;
    			if (pre.next != cur) {
    				pre.next  = cur.next;
    			} else {
					pre = pre.next;
				}
    		
    	}
    	ListNode.traverse("082", tHead.next);
        return tHead.next;
    }
	public static void main(String[] args) {
		_082_Remove_Duplicates_from_Sorted_List_II obj = new _082_Remove_Duplicates_from_Sorted_List_II();
//		obj.twoSum(new int[]{1, 2, 3, 4, 5, 6, 7}, 7);
//		obj.twoSum2(new int[]{2, 7, 11, 15}, 9);
//		obj.deleteDuplicates(ListNode.newLinkListWithDuplicatesElements());
		obj.deleteDuplicates(null);
	}

}
